package com.example.arithmeticleetcode.leetcode.nov;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-12-02 10:40
 **/
public class Fbnq {

    public static void main(String[] args) {
        int n = 45;
//        System.out.println(flib1(n));
//        System.out.println(flib2(n));
//        System.out.println(flib3(n));
//        System.out.println(flib4(n));
        System.out.println(flib5(n)); //
        System.out.println(flib6(n));
    }

    public static int flib1(int n) {
        if (n <= 2) return 1;
        return flib1(n - 1) + flib1(n - 2);
    }

    static int flib2(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[1] = array[2] = 1;
        return flib2(n, array);
    }

    private static int flib2(int n, int[] array) {
        if (array[n] == 0) {
            array[n] = flib2(n - 1, array) + flib2(n - 2, array);
        }
        return array[n];
    }

    static int flib3(int n) {
        int[] arr = new int[n + 1];
        arr[2] = arr[1] = 1;
        for (int i = 3, len = arr.length; i < len; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    static int flib4(int n) {
        int[] arr = new int[2];
        arr[1] = arr[0] = 1;
        for (int i = 3; i <= n; i++) {
            arr[i % 2] = arr[(i - 1) % 2] + arr[(i - 2) % 2];
        }
        return arr[n % 2];
    }

    /**
     * % 2 == & 1
     *
     * @param n
     * @return
     */

    static int flib5(int n) {
        int[] arr = new int[2];
        arr[1] = arr[0] = 1;
        for (int i = 3; i <= n; i++) {
            arr[i & 1] = arr[(i - 1) & 1] + arr[(i - 2) & 1];
        }
        return arr[n & 1];
    }

    static int flib6(int n) {
        if (n <= 2) return 1;
        int first = 1, second = 1;
        for (int i = 3; i < n; i++) {
            int temp = first;
            first = second;
            second = temp + second;
        }
        return first + second;
    }
}
